package com.zl.learning.arithmetic.leetcode;

import org.junit.Test;

import java.util.*;

public class Solution {

    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int need = target - nums[i];
            if (map.containsKey(need)) {
                return new int[]{nums[i], need};
            }
            map.put(nums[i], i);
        }
        return null;
    }

    @Test
    public void test1() {
        int[] num = new int[]{1, 6, 3, 7, 24, 11, 22};
        int[] res = twoSum(num, 10);
        System.out.println(Arrays.toString(res));
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    /**
     * 243
     * 564
     * 80
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        ListNode p1 = l1, p2 = l2, curr = head;
        int c = 0;
        while (p1 != null || p2 != null) {
            int a = p1 == null ? 0 : p1.val;
            int b = p2 == null ? 0 : p2.val;
            int sum = a + b + c;
            c = sum / 10;
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
            if (p1 != null) p1 = p1.next;
            if (p2 != null) p2 = p2.next;
        }
        if (c > 0) {
            curr.next = new ListNode(c);
        }
        return head.next;
    }

    @Test
    public void test2() {
        ListNode l1 = new ListNode(2);
        l1.next = new ListNode(4);
        l1.next.next = new ListNode(3);

        ListNode l2 = new ListNode(5);
        l2.next = new ListNode(6);
        l2.next.next = new ListNode(4);
        ListNode l3 = addTwoNumbers(l1, l2);
        while (l3 != null) {
            System.out.print(l3.val);
            l3 = l3.next;
        }
    }

    public String lengthOfLongestSubstring(String s) {
        Set<Character> occ = new HashSet<>();
        int len = s.length();
        int rk = 0;
        int acc = 0;
        int bk = 0;
        for (int i = 0; i < len; i++) {
            if (i != 0) {
                occ.remove(s.charAt(i - 1));
            }
            while (rk < len && !occ.contains(s.charAt(rk))) {
                occ.add(s.charAt(rk));
                ++rk;
            }
            if (acc < rk - i) {
                acc = rk - i;
                bk = i;
            }
        }
        return s.substring(bk, rk);
    }

    @Test
    public void test3() {
        String s = "abcabdecbasebdb";
        String res = lengthOfLongestSubstring(s);
        System.out.println(res);
    }

    public double findMedianSortedArrays(int[] A, int[] B) {
        int m = A.length;
        int n = B.length;
        if (m > n) { // to ensure m<=n
            int[] temp = A;
            A = B;
            B = temp;
            int tmp = m;
            m = n;
            n = tmp;
        }
        int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;
        while (iMin <= iMax) {
            int i = (iMin + iMax) / 2;
            int j = halfLen - i;
            if (i < iMax && B[j - 1] > A[i]) {
                iMin = i + 1; // i is too small
            } else if (i > iMin && A[i - 1] > B[j]) {
                iMax = i - 1; // i is too big
            } else { // i is perfect
                int maxLeft = 0;
                if (i == 0) {
                    maxLeft = B[j - 1];
                } else if (j == 0) {
                    maxLeft = A[i - 1];
                } else {
                    maxLeft = Math.max(A[i - 1], B[j - 1]);
                }
                if ((m + n) % 2 == 1) {
                    return maxLeft;
                }

                int minRight = 0;
                if (i == m) {
                    minRight = B[j];
                } else if (j == n) {
                    minRight = A[i];
                } else {
                    minRight = Math.min(B[j], A[i]);
                }

                return (maxLeft + minRight) / 2.0;
            }
        }
        return 0.0;
    }

    @Test
    public void test4() {
        int[] a = {1,2};
        int[] b = {3,4};
        double res = findMedianSortedArrays(a,b);
        System.out.println(res);
    }

}
